package com.wayne.leetcode.problems;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.TreeMap;

public class Solution456 {
  public static boolean find132pattern1(int[] nums) {
    int n = nums.length;
    if (n < 3) return false;
    // 左侧最小值
    int leftMin = nums[0];
    // 右边的所有元素
    TreeMap<Integer, Integer> rightAll = new TreeMap<>();
    for (int i = 2; i < n; i++) {
      rightAll.put(nums[i], rightAll.getOrDefault(nums[i], 0) + 1);
    }
    // 中间索引位置
    for (int j = 1; j < n - 1; j++) {
      // 符合 第二个值大于第一个值  只需要判断右边是否有一个大于第一个值又小于中间值的存在
      if (leftMin < nums[j]) {
        // ceilingKey 返回大于或等于给定键的最小键，如果没有这样的键，则null
        Integer next = rightAll.ceilingKey(leftMin + 1);
        if (next != null && next < nums[j]) {
          return true;
        }
      }
      // 最小值
      leftMin = Math.min(leftMin, nums[j]);
      // 提出第一个右边元素 作为中间比较值
      rightAll.put(nums[j + 1], rightAll.get(nums[j + 1]) - 1);
      // 如果 这个元素只有一个时拿出来后 需要删除这个节点
      if (rightAll.get(nums[j+1])==0) {
        rightAll.remove(nums[j+1]);
      }
    }
    return false;
  }

  public static boolean find132pattern(int[] nums) {
    int n = nums.length;
    if (n < 3) return false;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(nums[n-1]);
    int maxK = Integer.MIN_VALUE ;
    for (int i=n-2;i>=0;i--) {
      if (nums[i]<maxK) {
        return true;
      }
      while (!stack.isEmpty() && nums[i] > stack.peek()) {
        maxK = stack.pop();
      }
      if (nums[i]>maxK) {
        stack.push(nums[i]);
      }
    }
    return false;
  }
  public static void main(String[] args) {
    System.out.println(find132pattern(new int[]{1, 4, 3, 2}));
  }
}